package com.fjl.array.leetcode395;

import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/3/27 16:20
 */
/*
给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
如果不存在这样的子字符串，则返回 0。
示例 1：
    输入：s = "aaabb", k = 3
    输出：3
    解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2：
    输入：s = "ababbc", k = 2
    输出：5
    解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
 */
public class Clazz {
    public int longestSubstring(String s, int k) {
        int len = 0;
        for (int i = 1; i <= 26; i++) {
            // 限制窗口中只能有 i 种不同字符
            len = Math.max(len, logestKLetterSubstr(s, k, i));
        }
        return len;
    }

    private int logestKLetterSubstr(String s, int k, int count) {
        // 记录答案
        int res = 0;
        // 快慢指针维护滑动窗口，左闭右开区间
        int left = 0, right = 0;
        // 题目说 s 中只有小写字母，所以用大小 26 的数组记录窗口中字符出现的次数
        int[] windowCount = new int[26];
        // 记录窗口中存在几种不同的字符（字符种类）
        int windowUniqueCount = 0;
        // 记录窗口中有几种字符的出现次数达标（大于等于 k）
        int windowValidCount = 0;
        // 滑动窗口代码模板
        while (right < s.length()) {
            // 移入字符，扩大窗口
            char c = s.charAt(right);
            if (windowCount[c - 'a'] == 0)
                windowUniqueCount++;
            windowCount[c - 'a']++;
            if (windowCount[c - 'a'] == k)
                windowValidCount++;
            right++;
            while (windowUniqueCount > count) {
                // 移出字符，缩小窗口
                char d = s.charAt(left);
                if (windowCount[d - 'a'] == k)
                    windowValidCount--;
                windowCount[d - 'a']--;
                if (windowCount[d - 'a'] == 0)
                    windowUniqueCount--;
                left++;
            }
            if (windowValidCount == count)
                res = Math.max(res, right - left);
        }
        return res;
    }

    public static void main(String[] args) {
        Clazz clazz = new Clazz();
        System.out.println(clazz.longestSubstring("ababbc", 2));
    }
}
